package day_2022_9_to_12.Day;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author haomin
 * @date 2022/10/14 16:10
 **/
public class Day42_1_Num940_DistinctSubseqII {
    // dfs超时
    class Solution {
        Set<String> set = new HashSet<>();
        public int distinctSubseqII(String s) {
            dfs(s, 0, s.length(), new StringBuffer());
            return set.size() % 1000000007;
        }
        private void dfs(String s, int l, int r, StringBuffer sb){
            if(l > r) return;
            if(sb.length() != 0) {
                set.add(sb.toString());
            }
            for(int i = l; i < r; ++i){
                sb.append(s.charAt(i));
                dfs(s, i+1, r, sb);
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }
    class Solution2 {
        int mod = (int)1e9 + 7;
        public int distinctSubseqII(String s) {
            char[] c = s.toCharArray();
            int[] last = new int[26];
            long[] count = new long[c.length];
            Arrays.fill(last, -1);
            Arrays.fill(count, 1);
            for(int i = 0; i < c.length; ++i){
                for(int j = 0; j < 26; ++j){
                    if(last[j] >= 0)
                        count[i] += count[last[j]];
                }
                count[i] %= mod;
                last[c[i]-'a'] = i;
            }
            long ans = 0;
            for(int i = 0; i < 26; ++i){
                if(last[i] >= 0){
                    ans += count[last[i]];
                }
            }
            return (int)(ans % mod);
        }
    }
}